\section{Problema 2}

\subsection{Introducci\'on}


En este ejercicio debíamos calcular entre 2 investigadores la fracción de entusiasmo que tenía un investigador comparada con el otro en base a una ``red de amistades''. Lo pensamos como un grafo \footnote{http://en.wikipedia.org/wiki/Graph\_\%28mathematics\%29} en el cual los vértices son los investigadores y los ejes son las amistades. Básicamente debíamos calcular el camino mínimo\footnote{http://en.wikipedia.org/wiki/Shortest\_path} entre las amistades de ambos investigadores contando la cantidad de ejes como medidor de ``distancia''.

Para ello, decidimos usar el algoritmo de recorrido de grafos \textit{BFS} (Breadth-First Search)\footnote{http://en.wikipedia.org/wiki/Breadth-first\_search} con una pequeña modificación hecha por nosotros.


	   
\subsection{Desarrollo}

Nuestro algoritmo sigue la filosofía del \textit{BFS} de recorrer el grafo a lo ancho, o sea, lo va recorriendo de a ``niveles'' en vez de recorrer sin frenar hasta no poder más y despu\'es volver (como hace el DFS). Lo que modificamos nosotros fue que nuestro algoritmo cuando la iteraci\'on est\'a en un v\'ertice, numera a los vecinos (o ``hijos'') del vértice asignándoles uno más que su número. De esta forma, dado un vértice podemos calcular su distancia al resto. El algoritmo arranca con distancia 0 en el vértice inicial e infinito en el resto y va calculando las distancias en base al inicial.

A primera vista no se ve la relaci\'on entre BFS y este problema, pero mirémoslo como si fuera un Grafo en el cual cada amistad es un eje y cada investigador un v\'ertice y existe una relación de amistad entre 2 investigadores \textit{x} e \textit{y} si y sólo si existe un camino entre los vértices del grafo que representan a \textit{x} y a \textit{y}. Nos piden buscar \textit{la cantidad de veces que el entusiasmo original se verá fraccionado al 50\%} o devolver \textit{0} si no hay relación de amistad. Al explicar que en \textit{todo investigador [que no sea p] se genera un riguroso 50\% de la sensación de la más entusiasmada de sus amistades directas} nos están diciendo básicamente que mientras más larga sea la ``longitud del camino de amistad \textit{mínima}'', más fraccionado estará el entusiasmo original. Como puede haber más de un ``camino de amistades'' entre dos investigadores, debemos buscar el de longitud mínima. O sea, el de menor cantidad de ejes (amistades) entre \textit{p} y \textit{q}. Eso es exactamente lo que hace nuestro algoritmo modificado de BFS.
\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline 	\\ 
	 Entonces, el procedimiento sería el siguiente:
	\begin{compactenum}
		\item Aplicar una función biyectiva a los investigadores para identificarlos uno con uno con un vértice en el grafo. La vuelta también es posible de así requerirlo (de vértice en el grafo a nombre de investigador).
		\item Generar el grafo con sus vértices y ejes de tal manera que se pueda buscar en tiempo constante los vértices adyacentes a un vértice dado. Si dos investigadores son amigos sus respectivos vértices son adyacentes en el grafo y viceversa.
		\item Aplicar el algoritmo de BFS-modificado al grafo generado.
		\item Devolver la solución
	\end{compactenum}
	\\ \hline
    \end{tabular}
\end{center}
En el punto 1, por la forma que hicimos la funci\'on biyectiva, dado un \textit{vértice} podemos obtener su respectivo \textit{string} (nombre del investigador)  en tiempo constante. En cambio, la vuelta no es tan simple. Obtenemos el \textit{vértice} relacionado con un \textit{string} dado con complejidad igual a \textit{cantidad de investigadores} (tomando como constante a la comparación entre strings). De \textit{vértice} a \textit{string} tenemos un arreglo donde la \textit{i}-ésima posición representa al vértice \textit{i} del grafo y contiene el string respectivo. Para la vuelta (de \textit{string} a \textit{vértice}) recorremos el arreglo buscando la posición de éste que tenga el string buscado.

En el punto 2 la parte más importante de nuestra estructura es un \textit{vector} (o \textit{arreglo}) en el cual cada posición del vector representa a un vértice distinto y el contenido de cada una es una lista de los los vértices adyacentes al vértice representado por esta posición. De esta forma tenemos acceso aleatorio de tiempo constante a los adyacentes de cualquier vértice dado.

Los puntos 1 y 2 pertenecerían al constructor del grafo y el 3 a la función ``BFS-mod''.


\newpage

\subsection{Pseudoc\'odigo}
En el archivo \textbf{Grafo.java} podremos encontrar la clase ``Grafo'' con las funciones \textit{BFS-mod} y el constructor del grafo. En el archivo \textbf{Ej2.java} podremos encontrar la clase ``Ej2'' con la función principal que orquesta la leída, la ejecución y la escritura de la solución del problema.


\begin{parr}
\begin{algorithm}[H]
\caption{\operL{constructor-grafo}{ \vin{l}{lista de amistades}}{Grafo}}
\begin{algorithmic}[1]\parskip=1mm
\FOR{todas las amistades \textit{a} de \textit{l}}
	\STATE set.Agregar(\textit{a}.investigador\_1)
	\STATE set.Agregar(\textit{a}.investigador\_2)
\ENDFOR
\STATE \COMMENT{En set ya tengo el conjunto total de investigadores  sin repetir}
\FOR{cada investigador de set}
	\STATE asignarle una posición diferente en el arreglo de\_pos\_a\_investigador\_original
\ENDFOR
\STATE \textbf{var} set $\leftarrow$ Conjunto vacío de vértices sin repetidos (al agregar revisa)
\STATE \textbf{var} vértices $\leftarrow$ Vector de lista de vértices con longitud= cant vértices
\STATE \textbf{var} de\_pos\_a\_investigador\_original $\leftarrow$ Arreglo de Strings longitud= cant vértices
\FOR{todas las amistades \textit{a} de \textit{l}}
	\STATE \textbf{var} inv\_1 $\leftarrow$ \textit{a}.investigador\_1
	\STATE \textbf{var} inv\_2 $\leftarrow$ \textit{a}.investigador\_2
	\STATE \textbf{var} vertice\_1 $\leftarrow$ buscar en \textit{de\_pos\_a\_investigador\_original} la pos de \textit{inv\_1}
	\STATE \textbf{var} vertice\_2 $\leftarrow$ buscar en \textit{de\_pos\_a\_investigador\_original} la pos de \textit{inv\_2}
	\STATE Agregar a la lista de \textit{vertices}[\textit{vertice\_1}] el \textit{vertice\_2}; \COMMENT{vértice\_2 es adyacente a vértice 1}
	\STATE Agregar a la lista de \textit{vertices}[\textit{vertice\_2}] el \textit{vertice\_1}; \COMMENT{vértice\_1 es adyacente a vértice 2}
\ENDFOR
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item for líneas 4-7: $\theta\left(\vert l \vert * log(cantidad de investigadores)\right)$
	\item for lineas 9-11: $\theta\left(cantidad investigadores\right)$
	\item for lineas 12-19: $\theta\left(\vert l \vert * cantidad de investigadores\right)$ ya que para cada eje deberá buscar en todas las posiciones del arreglo \textit{de\_pos\_a\_investigador\_original} por el vértice correspondiente.
	\item resto de las líneas: O(1)
\end{compactitem}
\end{algorithm}


\begin{algorithm}[H]
\caption{\operL{BFS-mod}{ \vin{p}{vértice p}, \vin{q}{vértice q}, \vin{G}{Grafo}}{int}} \begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT{NOTA: revisa antes que p y q estén entre los investigadores. $\backslash$ }
\STATE \COMMENT{ Si alguno no está, devuelve 0 sin ejecutar el BFS}
\STATE \textbf{var} cola $\leftarrow$ cola vacía de v\'ertices
\STATE \textbf{var} distancias $\leftarrow$ array de enteros de longitud = cant vértices
%\STATE \textbf{var} padre $\leftarrow$ array de enteros \COMMENT{la uso sólo en demostración}
%\STATE padre[p] $\leftarrow$ INDEFINIDO \COMMENT{la uso sólo en demostración}
\STATE  distancias[p] $\leftarrow$ 0
\STATE  distancias[x] (\textit{$\forall x$} con \textit{x$\neq$p} )$\leftarrow$ INFINITO
\STATE cola.AgregarAtras(p)
\WHILE{cola $\neq \emptyset$}
	\STATE \textbf{var} v $\leftarrow$ cola.SacarPrimero()
	\FOR{todos los adyacentes \textit{w} de \textit{v}}
		\IF{distancias[\textit{w}] $==$ INFINITO}
			\STATE distancias[\textit{w}] $\leftarrow$ distancias[\textit{v}] + 1
			\STATE cola.AgregarAtras(\textit{w})
%			\STATE padre[w] $\leftarrow$ v
			\IF{\textit{w} == \textit{q}}
				\STATE break del for y del while
			\ENDIF
		\ENDIF		
	\ENDFOR
\ENDWHILE
\STATE return distancias[q]
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item líneas 6: rellenar el arreglo O($cantidad investigadores$)
	\item for líneas 10-18: O(grado de v)
	\item while lineas 8-19: O$\left(\vert cantidad de ejes \vert + cantidad de vertices\right)$ ya que en peor caso la cola llegará a tener longitud = cant. vértices y por cada vértice (investigador) iterará todos sus adyacentes y al final del while habrá revisado cada eje 2 veces en peor caso.
\end{compactitem}
\end{algorithm}


\end{parr}

%
\subsection{Demostración de la solución}
Cosas a tener en cuenta sobre BFS-mod
\begin{compactenum}
	\item Sólo agrego una vez los vértices a la cola. Esto se debe a que agrego un vértice si y sólo si lo estoy iterando y tiene distancia infinita. Una vez que lo agregué, agrego otra distancia y nunca más lo cambio; por lo que nunca más llegará a ser infinito.
	\item Agrego a todos los vecinos no visitados todavía de un vértice en la misma iteración. Como revisamos todos los vecinos antes de pasar al siguiente vértice, los agregaríamos al mismo tiempo y no los volveríamos a agregar por 1.
	\item Itero a todos los vértices de la componente conexa\footnote{http://en.wikipedia.org/wiki/Connected\_component\_\%28graph\_theory\%29} de p: inmediato de 1. y 2. 
\end{compactenum}

\textbf{Proposición}. BFS-mod calcula la cantidad de ejes mínima que se necesitan recorrer para ir desde p hasta q. \\
D// Analicemos el caso conexo y además el problema como si BFS-mod fuera generando un árbol a medida que va iterando los vértices (como realmente hace el BFS guardándose la información necesaria). En la primer iteración, la del vértice p, asigna a todos los vecinos de p la distancia 1 que sería la distancia de su padre más 1 (p empieza con distancia 0).

Veamos ahora el caso general mirando el árbol como en ``niveles''.
\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/demo-png.pdf,width=0.7\linewidth,clip=}
\caption{Idea árbol BFS con sus diferentes niveles.}
\end{figure}

Para todos los vértices del nivel \textit{i+1} la distancia es esa misma, \textit{i+1}, que sería la distancia desde p hasta los vértices de nivel 1 más 1.

Asumamos que no. Asumamos que hay un camino que recorre una menor cantidad de ejes que el del árbol BFS. En otras palabras, existe otro camino con longitud menor a \textit{i+1} para algún vértice \textit{v} de nivel \textit{i+1}. Este camino debe tener ejes en el grafo. No pueden ser adyacentes \textit{v} y \textit{p} porque sino por ``2.'' le hubiera asignado longitud 1 cuando iteré a \textit{p} y pertenecería al nivel 1. Tampoco podría ser adyacente a los vértices de los niveles \textit{2} hasta \textit{i-1} por ``1.'' y ``2.'' ya que iteré todas las adyacencias de todos estos niveles y sólo agrego vértices a la cola 1 vez. Lo único que nos queda es que recién ``encuentre la forma de llegar a \textit{v}'' cuando vea los vecinos de su padre el cual pertenece al nivel \textit{i}. En otras palabras, no existe otro camino más corto que recorriendo los niveles del BFS. Por ende, la longitud del camino mínimo desde \textit{p} hasta \textit{q} es \textit{i+1}.

\subsection{Complejidad (modelo uniforme)}
Como podremos ver en el análisis de ambos algoritmos, el constructor del grafo y el BFS-mod, la complejidad sería $\theta\left(\vert cantidad de amistades \vert * cantidad de investigadores\right)$ y $\theta\left(\vert cantidad de amistades \vert + cantidad de investigadores\right)$ respectivamente. Esto se debe a que son las mayores complejidades de las líneas de su ejecución y hacen despreciables a las demás. Finalmente la complejidad del constructor haría lo mismo con la del BFS-mod ya que crece mucho más rápido dejando como complejidad final a $\theta\left(\vert l \vert * cantidad de investigadores\right)$. No consideramos que haya un peor caso ya que el constructor siempre hará lo mismo, la misma ejecución, sin importar las características de los investigadores y/o sus amistades entre sí. Podemos decir tal afirmación ya que no hay \textit{ifs} que hagan diferir de forma considerable la complejidad dependiendo del resultado de la guarda de estos y los \textit{fors} tienen un tiempo de ejecución fijo.

Esto parecería raro a primera vista, ya que la complejidad de la parte ``interesante'' del algoritmo es mucho menor que algo que parecería trivial. El problema es que aunque lo parezca no era trivial. No teníamos asegurado el orden de los vértices en la entrada ya que recibíamos los ejes en una lista de adyacencia. Además, no podíamos asegurar que no vengan repetidos y en muchos casos seguro que vendrían repetidos.

Aun así, la complejidad cumple con el máximo pedido por la cátedra.

\subsection{Tests}
Ya que el algoritmo no cambia su complejidad de forma considerable con diferentes familias de casos y el mismo tamaño de entrada decidimos hacer 3 tipos de casos que parecerían importantes:
\begin{compactitem}
	\item Grafo completo: los investigadores son todos amigos entre sí uno con uno
	\item Grafo disperso: las cantidad de amistades es igual a \textbf{30/100 por n * (n - 1) / 2}. O sea, el 30\% de los ejes que tendría un completo de ese tamaño. Decidimos el 30\% porque para grafos con un n no demasiado grande se podría seguir considerando disperso (no crece de forma lineal la diferencia).	
	\item Árbol: las cantidad de amistades es igual a \textbf{(n - 1)}
\end{compactitem}

En otras palabras, fijamos el m (cant amistades) y fuimos variando el n (cantidad investigadores). Además elegimos ver qué pasaría si p y q están entre los investigadores, uno no está o ambos no están. Analizaremos estos 3 sub-casos para los 3 casos mencionados anteriormente.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/completos-png.pdf,width=0.9\linewidth,clip=}
\caption{Tests para grafos completos.}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/disperso-png.pdf,width=0.9\linewidth,clip=}
\caption{Tests para grafos dispersos.}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej2/arbol-png.pdf,width=0.9\linewidth,clip=}
\caption{Tests para árboles.}
\end{figure}

Como podremos ver, pudimos acotar el crecimiento de la complejidad empírica de nuestro algoritmo por la complejidad teórica. En el caso de los completos no necesitamos multiplicar las variables por una constante mayor a 0 sino que sólo necesitamos sumar 4,000 para acomodar mejor la ubicación. En el caso de los dispersos hasta tuvimos  que multiplicar por una constante menor a 0 para que no crezca demasiado rápido y no se aprecie bien el gráfico por la diferencia que quedaría entre la función propuesta y los datos nuestros.

Lo más remarcable es la diferencia del gráfico de árboles con los otros 2. Claramente toma tiempo mucho menor ... acaso no es un mejor caso, y por ende, los otros dos son peor caso? En verdad esto se debe a que el tamaño de entrada del caso de los árboles es MUCHO menor ya que es tanta la diferencia de ejes que el gráfico miente. La complejidad sigue siendo la misma pero el m es mucho más chico y multiplica menos la cantidad de ejecuciones; a eso se debe esta ``peculiaridad''. O sea, estamos comparando diferentes tamaños de entrada, básicamente, entre los 3 grafos. La idea era remarcar que no importa la familia, nuestro algoritmo trabajaría en un tiempo que podía ser acotado por nuestra complejidad teórica.

Aun así, nos sirve el gráfico de árboles ya que como los valores no son tan altos podemos apreciar mejor la diferencia entre los 3 sub-casos que dependían si p y/o q estaban o no. Podemos observar, por curiosidad simplemente porque esto excede a lo pedido, que en el caso de que ambos están es un poco mayor a los otros 2 casos. Esto simplemente es porque los otros 2 casos \textbf{no} ejecutan el algoritmo de BFS-mod porque antes de entrar preguntan si es necesario, o sea, si ambos p y q pertenecen a los investigadores. Si alguno de los 2 no está, devolvería 0 simplemente. En cambio, cuando ambos están sí o sí debería ejecutar el algoritmo de BFS-mod para encontrar la longitud del camino mínimo.

\subsection{Conclusiones}
En conclusión, el algoritmo, aunque simple, es un buen ejemplo de los problemas en los que lo que parece trivial termina haciendo la diferencia y lo que parecía importante termina siendo despreciable. Por lo menos en el tema de la complejidad.
Además, los tests confirmaron nuestras predicciones sobre la complejidad del algoritmo y no mostraron ningún tipo de \textit{outlier} ni sorpresas.
%
%
%
